{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.core.display import display, HTML\n",
    "display(HTML(\"<style>.container { width:100% !important; }</style>\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lecture 7 - Classification, Generalization, Overfitting, Evaluation, Cross-validation and Scikit-learn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Content"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Classification\n",
    "2. Generalization\n",
    "3. Overfitting\n",
    "4. Classifiers goodness-of-fit\n",
    "5. Cross-validation\n",
    "6. Comparing multiple classifiers\n",
    "7. Scikit-learn\n",
    "8. No Free Lunch Theorem\n",
    "9. Feature Selection\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Learning Outcomes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At the end of this lecture, you should be able to:\n",
    "\n",
    "* explain the difference between classification and regression\n",
    "* explain the theory of generalization, the phenomenon of overfitting, and the 'no free lunch' theorem\n",
    "* discuss and apply various measures for evaluating classifier accuracy\n",
    "* use cross-validation for training and evaluating classifiers\n",
    "* compare the accuracies of multiple classification algorithms across multiple datasets\n",
    "* explain the rationale of feature selection and apply it \n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In machine learning, classification is the task of devising a *classifier* capable of assigning a particular class/category to an unknown instance/sample from a set of possible classes. A machine learning algorithm builds, evaluates and optimises a classifier on the training data in  such a way that it discriminate instances of different classes from each other, in the hope that these patterns will *generalise* and be valid on data which the algorithm has not *seen* during the training phase. \n",
    "\n",
    "Classification (like regression) belong to a family of **supervised learning** methods. In order to be able to perform supervised learning, a training set is required where all of the samples' **class values are known in advance**. The classifier is **trained** to learn how to map each of the samples' features/attributes to their corresponding class labels.\n",
    "\n",
    "Once the classifier is trained to do this on a fully labelled dataset, the classifier is then used to classify unknown samples into class labels given the samples feature vectors only. If there are two classes used in the prediction, then this is referred to as a **binary classification problem**. If there are more than just two classes in the dataset, this is than called a **multiclass classification problem**. \n",
    "\n",
    "As the number of classes in a prediction problem increase, so does the difficulty in maintaining high accuracy. \n",
    "\n",
    "A classifier can be fixed-size, irrespective of the amount of data provided for training. These algorithms are called parametric. Classifiers can also be variable in size, and thus grow in complexity with the amount of available data, allowing it to capture and encode complex decision boundaries. These algorithms are referred to as non-parametric.\n",
    "\n",
    "Classification is an immensely vital and widely used technique. Examples of classification are found in classifying whether or not a given email is of a class \"spam\" or \"non-spam\"; banks use it to classify if a given transaction is \"legitimate\" or \"fraudulent\" class; medical staff have technologies to assigning a diagnosis to a given patient as described by observed characteristics of the patient; financial analysts use it to predict if a given stock should be classified as \"invest now\" or \"do not invest\" at a given point in time given a range of accompanying indicators. \n",
    "\n",
    "In order to perform classification, an algorithm is first needed that creates a classifier. There are many types of machine learning classification algorithms. \n",
    "\n",
    "We have looked kNN and seen how it can be used as a classification algorithm. Some of the other well known ones are Neural Networks, Support Vector Machines, Tree classifiers, Boosted Ensembles, Bagging, Random Forests as well as Naive Bayes.\n",
    "\n",
    "A good summary in a form of a mind map of various sort of algorithms that exist can be seen here:\n",
    "\n",
    "![Jason Brownlee http://machinelearningmastery.com/parametric-and-nonparametric-machine-learning-algorithms/ ](../figures/algorithms.jpg)\n",
    "\n",
    "> Source: Jason Brownlee http://machinelearningmastery.com/parametric-and-nonparametric-machine-learning-algorithms/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parametric and non-parametric classification algorithms in machine learning\n",
    "\n",
    "Machine learning algorithms can be broadly categorised into parametric and non-parametric algorithms.  \n",
    "\n",
    ">    A learning model that summarizes data with a set of parameters of fixed size (independent of the number of training examples) is called a parametric model. No matter how much data you throw at a parametric model, it won’t change its mind about how many parameters it needs. — Artificial Intelligence: A Modern Approach\n",
    "\n",
    "**Parametric algorithms** make strong assumptions about the data and are fixed in their complexity/size. Algorithms of this type are:  Logistic Regression,  Perceptron, Neural Networks and Naive Bayes.\n",
    "\n",
    "There are some advantages and disadvantages associated with these types of algorithms. They tend to be simpler due to few parameters and can be more interpretable. They are also faster to train on average and may require smaller datasets. Their weakness is their inflexibility and the highly constrained form, which, if unsuitable for the particular problem, will generate a poor fit. Often, these kinds of algorithms are more suited to less complex domains.\n",
    "\n",
    "\n",
    "**Non-parametric machine learning algorithms** do not make strong assumptions about the form of the mapping function that maps features to class labels. Because of this, they have more flexibility in learning the decision boundaries. These kinds of algorithms are good, when you do not have much prior knowledge about the data and have access to reasonably large datasets.\n",
    "\n",
    ">Nonparametric methods are good when you have a lot of data and no prior knowledge, and when you don’t want to worry too much about choosing just the right features. — Artificial Intelligence: A Modern Approach\n",
    "\n",
    "Some examples of non-parametric machine learning algorithms are: k-Nearest Neighbors, Boosting, Decision Trees, Random Forest, SVM. \n",
    "\n",
    "Benefits of these algorithms come in their flexibility and the absence of strong assumptions needed to do training. Also, they tend to have stronger performances. The down side to them is that they do require more data and runtime to train. Their biggest disadvantage would be their propensity to overfit.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example dataset - Wine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will return to the Wine dataset to explore classification."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib as mtpl\n",
    "import seaborn as sns\n",
    "\n",
    "\n",
    "%matplotlib inline\n",
    "\n",
    "df = pd.io.parsers.read_csv(\n",
    "    '../datasets/wine_data.csv',\n",
    "     usecols=[0,6,7]\n",
    "    )\n",
    "\n",
    "df.columns=['Class','Magnesium','Flavanoids']\n",
    "\n",
    "df['Class'].replace('3', 0, inplace=True)\n",
    "df.to_csv('../datasets/wine_data_test.csv', header=None, index=None)\n",
    "\n",
    "df.head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Confirm we have 3 class labels:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.Class.unique()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Confirm data types:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.dtypes\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get counts for each class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.groupby('Class').count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.groupby('Class').count() / df.groupby('Class').count()['Magnesium'].sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In classification problems, the **ability to separate classes** from one another is the most important consideration. Histograms of the feature values per class type, can be a useful tool for **eyeballing** some features and to get a rough feeling for their **discriminative power**. \n",
    "\n",
    "Here we are visualising the histograms of the two features for each of the three classes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib import pyplot as plt\n",
    "plt.figure(figsize=(10,8))\n",
    "\n",
    "colors = ('blue', 'red', 'green')\n",
    "\n",
    "for label,color in zip(range(0,3), colors):\n",
    "    mean = np.mean(df['Magnesium'][df['Class'] == label]) # class sample mean\n",
    "    stdev = np.std(df['Magnesium'][df['Class'] == label]) # class standard deviation\n",
    "    df['Magnesium'][df['Class'] == label].hist(alpha=0.3, # opacity level\n",
    "             label='class {} ($\\mu={:.2f}$, $\\sigma={:.2f}$)'.format(label, mean, stdev), \n",
    "             color=color,\n",
    "             bins=15)\n",
    "\n",
    "plt.title('Wine data set - Distribution of Magnesium content')\n",
    "plt.xlabel('Magnesium content', fontsize=14)\n",
    "plt.ylabel('count', fontsize=14)\n",
    "plt.legend(loc='upper right')\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "plt.figure(figsize=(10,8))\n",
    "\n",
    "colors = ('blue', 'red', 'green')\n",
    "\n",
    "for label,color in zip(range(0,3), colors):\n",
    "    mean = np.mean(df['Flavanoids'][df['Class'] == label]) # class sample mean\n",
    "    stdev = np.std(df['Flavanoids'][df['Class'] == label]) # class standard deviation\n",
    "    df['Flavanoids'][df['Class'] == label].hist(alpha=0.3, # opacity level\n",
    "             label='class {} ($\\mu={:.2f}$, $\\sigma={:.2f}$)'.format(label, mean, stdev), \n",
    "             color=color,\n",
    "             bins=15)\n",
    "\n",
    "plt.title('Wine data set - Distribution of Flavanoids content')\n",
    "plt.xlabel('Flavanoids content', fontsize=14)\n",
    "plt.ylabel('count', fontsize=14)\n",
    "plt.legend(loc='upper right')\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see classification on this dataset in action.\n",
    "\n",
    "We will use the knn classifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import neighbors\n",
    "from sklearn.neighbors import KNeighborsClassifier\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn import preprocessing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will first normalise all the features using standardisation with the built in method provided by scikit-learn: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "std_scale = preprocessing.StandardScaler().fit(df[['Flavanoids', 'Magnesium']].dropna())\n",
    "X = std_scale.transform(df[['Flavanoids', 'Magnesium']].dropna())\n",
    "X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above gives us our X values that are our features.\n",
    "\n",
    "Next we extract the corresponding class values for each value of x:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "y = df.Class\n",
    "y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now train our classifier on our training dataset:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn_classifier = KNeighborsClassifier(n_neighbors=5, metric='euclidean')\n",
    "knn_classifier.fit(X, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Having trained our classifier, we now need to see how well it has trained. \n",
    "\n",
    "For this we use the same dataset that we trained the classifier on. This dataset is called the training dataset. \n",
    "\n",
    "We ask the classifier to predict the class label for each of the x values in our training dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "classification_results = knn_classifier.predict(X)\n",
    "classification_results"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above shows all the classifications/prediction that the classifier makes for each value x.\n",
    "\n",
    "We can put this into the original dataframe for later analysis:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df['Classification'] = classification_results\n",
    "df.head(30)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can calculate the overall accuracy of our training error on the training dataset which is one way of summarising the effectiveness of our training and is an important step in evaluating classifier training before moving forward to next steps."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn_classifier.score(X, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Valid questions now are:\n",
    "\n",
    "1. What does the classification accuracy of a classifier on a training dataset tell us about how accurate it will be on data which is outside of the training dataset?\n",
    "\n",
    "2. How can we be confident that our classifier will perform to similar levels of accuracy on data it has not been trained on?\n",
    "\n",
    "3. Will the classifier generalize beyond the training dataset?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Generalization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The goal of training a classifier, or creating a predictive model on a particular dataset is not so that it would make accurate predictions only on these samples. To use an absurd scenario, we could potentially create a look-up table, or an immense set of if-else statements for every example in a dataset and thereby achieve 100% accuracy. This process would be called memorising the data and is practically useless for the task of predictive analytics.\n",
    "\n",
    "Instead, the **goal is that the classifier would uncover and encode patterns describing the underlying structural relationships, with the intention of them generalising and thus being able to accurately predict data that the algorithm has not previously \"seen\"**. This is referred to as  generalization. In essence, machine learning is the attempt to take the limited amount of information it can gather and generalise. It embodies the movement from the 'specific to the general'.\n",
    "\n",
    "Generalization is the property of a classifier or modelling process, whereby the classifier is relevant for prediction purposes on data that were not used to train it. We must keep in mind that every dataset is a finite sample of a total population for a given domain (unless you have a dataset that contains all samples that will ever be used to describe a given problem.). And we want the classifier to be fit-for-purpose on the population of a given domain as a whole.\n",
    "\n",
    "Hence, **creating a classifier that is perfectly accurate on one training dataset is no guarantee of it being accurate at predicting unseen samples**. In fact, machine learning algorithms are notoriously susceptible to finding meaningless, or phantom patterns that are random idiosyncrasies within a given dataset sample, and have no value beyond the data outside of the training dataset. \n",
    "\n",
    "Sometimes we may have concerns that the training data were not representative of the true population which leads to bad generalization - and this does happen, often. The data can be noisy (mislabelled or erroneous data), have lots of outliers (valid but extreme values). But often it is the case that the algorithm used to train a classifier or build a model, created too good of a \"fit\" (too complex) on the training dataset that is ultimately useless and misleading beyond the samples it trained on.\n",
    "\n",
    "Training classifiers which are variable-size (optimisable) and can thus increase in complexity, often leads to the pattern below. Both the training and generalisation (test) error decrease initially during the early stages of classifier training. If the training ceases too early, then the classifier has usually not been given enough time to learn the separating class decision boundary sufficiently. This is referred to as underfitting. As the training algorithm builds a more complex classifier (model), the training error will continue to decrease. As the training error approaches zero, the training algorithm is said to 'converge'. However, complete convergence does not necessarily mean that the classifier will generalise well. It is usually quite easy to achieve full convergence on a training set. The difference between the final training error (convergence) and the generalisation (test) error is the indicator of the degree of overfitting that has occurred. \n",
    "\n",
    "Generalisation error will always be greater than the training error. However, we want this difference to be as small as possible.   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Source Wikipedia](../figures/generalization_overfitting.jpg)\n",
    "\n",
    "Source: Janert, P. K. (2010). Data analysis with open source tools.  O'Reilly Media, Inc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Overfitting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Overfitting is usually what happens when classifier generalization is not achieved**. It is the tendency of machine learning and data mining algorithms to tailor classifiers to the training data, at the expense of generalization to previously unseen data points. \n",
    "\n",
    "It should be noted that inherent within all machine learning and data mining algorithms is the tendency to overfit to some degree. Some algorithms will accentuate this tendency more than others and it will often depend on the dataset and the type of the problem.\n",
    "\n",
    "If we try hard enough and push the classifiers to become more and more complex, the algorithms will invariably find patterns in a dataset. The Nobel Laureate Ronald Coase one said\n",
    "\n",
    "> “If you torture the data long enough, it will confess.”\n",
    "\n",
    "The problem of overfitting is probably one of the greatest challenges for a data scientist.\n",
    "\n",
    "> The answer is not to use a data mining procedure\n",
    "that doesn’t overfit because all of them do. Nor is the answer to simply use models\n",
    "that produce less overfitting, because there is a fundamental trade-off between model\n",
    "complexity and the possibility of overfitting. Sometimes we may simply want more\n",
    "complex models, because they will better capture the real complexities of the application\n",
    "and thereby be more accurate. There is no single choice or procedure that will eliminate\n",
    "overfitting. The best strategy is to recognize overfitting and to manage complexity in a\n",
    "principled way.\n",
    "\n",
    "Provost, F., & Fawcett, T. (2013). Data Science for Business: What you need to know about data mining and data-analytic thinking. \" O'Reilly Media, Inc.\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from time import sleep\n",
    "from datetime import datetime\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.model_selection import train_test_split\n",
    "import seaborn as sns\n",
    "from pylab import rcParams\n",
    "\n",
    "rcParams['figure.figsize'] = 18, 10\n",
    "rcParams['font.size'] = 20\n",
    "rcParams['figure.dpi'] = 350\n",
    "rcParams['lines.linewidth'] = 2\n",
    "rcParams['axes.facecolor'] = 'white'\n",
    "rcParams['patch.edgecolor'] = 'white'\n",
    "rcParams['font.family'] = 'StixGeneral'\n",
    "\n",
    "wine_df = pd.read_csv(\n",
    "    '../datasets/wine_data.csv'\n",
    "    )\n",
    "\n",
    "X = wine_df.iloc[:, 1:]\n",
    "y = wine_df.iloc[:, :1]\n",
    "\n",
    "treeclf = DecisionTreeClassifier(max_depth=1, random_state=1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "training_error = pd.Series([1.0])\n",
    "test_error = pd.Series([1.0])\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=2, test_size=0.5)\n",
    "for i in range(1,13):\n",
    "    treeclf = DecisionTreeClassifier(max_depth=i, random_state=i)\n",
    "    training_error[i] = 1.0 - treeclf.fit(X_train, y_train).score(X_train, y_train) \n",
    "    test_error[i] = 1.0 - treeclf.fit(X_train, y_train).score(X_test, y_test) \n",
    "    plt.plot(training_error)\n",
    "    plt.plot(test_error)\n",
    "    plt.title('Generalisation, Convergence and Overfitting Example on Wine Dataset', size=30)\n",
    "    plt.xlabel('Classifier Complexity (Decision Tree Depth)', size=25)\n",
    "    plt.ylabel('Error Rate / Misclassification Rate', size=25)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bias-Variance Tradeoff "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![https://www.kdnuggets.com/2016/08/bias-variance-tradeoff-overview.html ](https://www.kdnuggets.com/wp-content/uploads/bias-and-variance.jpg) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Classifier Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to be able to ascertain if our classifier is both learning the training dataset (converging) or overfitting on previously unseen data, we need to have some evaluation metrics at our disposal. \n",
    "\n",
    "Fortunately the field of machine learning and data mining has been around for a long time so there are some very well established metric that enables us to evaluate our classifiers.\n",
    "\n",
    "Multiclass classification problems are treated similarly, however, there is usually a greater need in multiclass problems to break down the classification results at per-class label level in order to examine the performance. This is often necessary in the presence of unbalanced class distributions. \n",
    "\n",
    "A binary class **confusion-matrix** is a good starting point to visualize and understand the performance of a classifier. Each column of the matrix represents the instances in a predicted class, while each row represents the instances in an actual class. The name stems from the fact that it makes it easy to see if the system is confusing two classes (i.e. commonly mislabelling one as another)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![Source Wikipedia](../figures/confusion_matrix.jpg)\n",
    "\n",
    "Source: http://en.wikipedia.org/wiki/Confusion_matrix\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Source Wikipedia](../figures/classification_terms.jpg)\n",
    "\n",
    "Source: http://en.wikipedia.org/wiki/Confusion_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Accuracy\n",
    "\n",
    "Is the most commonly used metric. It is simplistic but useful as the first step. It is the number of correctly classified samples divided by all the samples in the dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Given the Wine dataframe from above, write a function that accepts it and returns the overall accuracy for the dataset:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_accuracy(df):\n",
    "    #your code here\n",
    "\n",
    "    return  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "calculate_accuracy(df)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The opposite of accuracy is the *error rate* and is reported quite often in literature. It is simply 1 - accuracy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recall\n",
    "\n",
    "Evaluates how many samples that belong to a particular class as actually classified as belonging to that class."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Given the Wine dataframe from above, write a function that accepts it and returns the recall (aka hit rate) for each class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_recall_per_class(df):\n",
    "    recall = {}\n",
    "    #your code here\n",
    "\n",
    "        \n",
    "    return recall"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "calculate_recall_per_class(df)\n",
    "#should return something like:\n",
    "#{1: 0.9322033898305084, 2: 0.6619718309859155, 3: 0.875}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## False Positive Rate\n",
    "\n",
    "False positive looks at the proportion of samples that are being incorrectly classified as belonging to a particular class, out of all samples that do not belong to that class."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Given the Wine dataframe from above, write a function that accepts it and returns the false positive rate for each class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_false_positive_rate_per_class(df):\n",
    "    fp_rate = {}\n",
    "    #your code here\n",
    "\n",
    "        \n",
    "    return fp_rate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "calculate_false_positive_rate_per_class(df)\n",
    "#should return something like:\n",
    "#{1: 0.13445378151260504, 2: 0.09345794392523364, 3: 0.06153846153846154}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Precision\n",
    "\n",
    "Precision takes into account the false positive classifications together with the true positive classifications."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Given the Wine dataframe from above, write a function that accepts it and returns the precision rate for each class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_precision_per_class(df):\n",
    "    precision = {}\n",
    "    #your code here\n",
    "\n",
    "        \n",
    "    return precision"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "calculate_precision_per_class(df)\n",
    "#should return something like:\n",
    "#{1: 0.7746478873239436, 2: 0.8245614035087719, 3: 0.84}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## F1-score\n",
    "\n",
    "Another important measure that is insightful in respect to the accuracy of each given class label is the F-value (known also as the F-measure or the F1-score).\n",
    "\n",
    "F1-score is particularly important for datasets with uneven class distributions. Training classifier on such problem is very difficult and all algorithms struggle to produce classifiers that accurately generalise on all class labels within such datasets. Usually the classes with the smallest number of samples experience the worst generalisation. The F1-score to some degree provides a more balanced assessment of a classifier's generalisation for each class label as it is the harmonic mean of the recall and precision values. The harmonic mean is a useful ttype of an average to use in this instance, since, unlike the arithmetic mean, the harmonic mean gives less significance to high-value outliers–providing a truer picture of the average.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Given the Wine dataframe from above, write a function that accepts it and returns the f1-score for each class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_f1score_per_class(df):\n",
    "    f1score = {}\n",
    "    #your code here\n",
    "\n",
    "        \n",
    "    return f1score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "calculate_f1score_per_class(df)\n",
    "#should return something like:\n",
    "#{1: 0.8461538461538461, 2: 0.734375, 3: 0.8571428571428571}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Confusion Matrix\n",
    "\n",
    "In a **multiclass scenario**, the binary confusion matrix seen above can easily be extended it an $n \\times n$ matrix where $n$ is the number of classes. \n",
    "\n",
    "In a multiclass setting it is particularly informative to know which classes are being misclassified as labels of another class. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Given the Wine df_result from above, write a function that accepts it and returns a confusion matrix data frame:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_confusion_matrix(df):\n",
    "    #your code here\n",
    "            \n",
    "    return \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "calculate_confusion_matrix(df)\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "#SHOULD RETURN\n",
    "    1 \t2 \t3\n",
    "1 \t55 \t4 \t0\n",
    "2 \t16 \t47 \t8\n",
    "3 \t0 \t6 \t41"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Geometric Mean"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Often though, on class-unbalanced problems, it is necessary to derive a single value to express the accuracy of a dataset. In these cases the total error (or accuracy) metrics as completely inadequate and a very good alternative is the Geometric mean of the recall values is defined as follows:\n",
    "\n",
    "\n",
    "<div style=\"font-size: 120%;\">  \n",
    "$Geometric\\ mean = \\left(\\prod_{i=1}^n Recall_i \\right)^{1/n}$\n",
    "</div>\n",
    "\n",
    "The geometric mean gives a more conservative mean then the arithmetic mean and is thus more appropriate, hence its usage. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Write a function that calculates the geometric mean for the data frame below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_geometric_mean(df):\n",
    "    gmean = 1.0\n",
    "    recall = calculate_recall_per_class(df)\n",
    "\n",
    "    #YOUR CODE HERE \n",
    "\n",
    "   \n",
    "    return np.power(gmean, 1.0 / float(len(recall)))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "calculate_geometric_mean(df)\n",
    "#SHOULD PRODUCE 0.8143030848180245\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cross-Validation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Under generalization and overfitting, we discussed the importance of developing classifiers that do not just remember the training data but are able to generalize on data that the machine learning algorithms had not previously seen. One solution is to split datasets into training and test sets. The training is performed on one, and the generalization is determined on the other.\n",
    "\n",
    "There are some problems with doing it this way. By defining  two sets, we reduce the number of samples which can be used for learning the model, and the results can depend on a particular random choice for the pair of (train, test) sets. Also, what proportion of data do we use for training and what for testing?\n",
    "\n",
    "Another approach which is more robust, is to split the whole data several consecutive times in different\n",
    "train set and test set combinations, and to return the averaged value of the prediction\n",
    "scores obtained with the different sets. This technique is called **k-fold cross-validation**. Where the k determines the number segments that the data is to be split into. In this procedure, 1 fold is retained for testing the classifier and the other k-1 folds are used for training.\n",
    "\n",
    "In the image example below, k=4 (4 folds). The classifier will be trained on the combination of 3 folds and  evaluated on the 4th fold (the test fold). This procedure is then repeated 4 times until every fold has been used as the test set once so that we can eventually calculate the average error rate of our model from the error rate of every iteration, which gives us an idea of how well our model generalizes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![Source Wikipedia](../figures/cross-validation-001_small.png)\n",
    "\n",
    "Source: https://github.com/rasbt/pattern_classification/blob/master/machine_learning/supervised_intro/images/cross-validation-001_small.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Keep in mind that the algorithm at all times is provided with the correct answers, but when the algorithm makes predictions, it does not refer to them, but instead uses the correct answers only to compare its own prediction to.\n",
    "\n",
    "Give the serious problem of class-imbalanced datasets, the most robust way to implement the above procedure is by using what is called the **stratified k-fold cross-validation**. By stratified, we mean that every fold will not only be of equal size as the other folds in terms of the number of samples, but every fold will also have an identical distribution of all class labels.\n",
    "\n",
    "Overall, the cross-validation approach can be computationally expensive but it is worth the extra effort and it does not waste too much data\n",
    "when creating the classifiers as it occurs  when fixing an arbitrary test set. This is an advantage in problems where the number of samples is very small. The question once you have trained and tested all your k classifiers is, which classifier to deploy in your application?\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Write a function that takes a dataframe, number of folds, column index that contains class labels, the number of features, number of classes, as well as the file name. The function will then create k stratified folds for cross-validation and write each individual fold to file with an appropriate name. Output for each class and each fold how many samples are being written so that you can confirm that your function is working."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cross_fold_file_generator(df, kfolds, class_index, num_of_features, num_of_classes, file_stem):\n",
    "    file_name = ['fold_' + str(x) for x in range(kfolds)]\n",
    "    \n",
    "     #your code here\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For our wine dataset, the function should produce something like the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cross_fold_file_generator(df, kfolds = 5, class_index = 0, num_of_features = len(df.columns) - 1, num_of_classes = len(df['Class'].unique()), file_stem = '../datasets/wine_xfold_')\n",
    "\n",
    "#should generate something like:\n",
    "#class:  1 fold:  0 samples:  12\n",
    "#class:  1 fold:  1 samples:  12\n",
    "#class:  1 fold:  2 samples:  12\n",
    "#class:  1 fold:  3 samples:  12\n",
    "#class:  1 fold:  4 samples:  11\n",
    "#class:  2 fold:  0 samples:  14\n",
    "#class:  2 fold:  1 samples:  14\n",
    "#class:  2 fold:  2 samples:  14\n",
    "#class:  2 fold:  3 samples:  15\n",
    "#class:  2 fold:  4 samples:  14\n",
    "#class:  0 fold:  0 samples:  10\n",
    "#class:  0 fold:  1 samples:  10\n",
    "#class:  0 fold:  2 samples:  9\n",
    "#class:  0 fold:  3 samples:  10\n",
    "#class:  0 fold:  4 samples:  9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using sci-kit learn's evaluation metrics and dataset splitting functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All that we have covered above is conveniently implemented for us in sci-kit learn."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can train a kNN classifier again on all our training data as follows and use the model for prediction:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn_classifier = knn_classifier.fit(df[['Magnesium','Flavanoids']], df['Class'])\n",
    "knn_classifier\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can find out how well our classifier learned the training dataset based on overall accuracy:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn_classifier.score(df[['Magnesium','Flavanoids']], df['Class'])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or we can use the classifier to classifier individual samples:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "inputs = np.array([2.2, 3.3]) \n",
    "print('Predicted class: ', knn_classifier.predict(inputs.reshape(-1, 2))[0])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we want to split the dataset into a training and test set with the test set comprising 20% is the dataset, we do as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# split into training and testing sets\n",
    "from sklearn.model_selection import train_test_split\n",
    "X_train, X_test, y_train, y_test = train_test_split(df[['Magnesium','Flavanoids']], df['Class'], random_state=1, test_size=0.2)\n",
    "\n",
    "print(X_train.shape)\n",
    "print(X_test.shape)\n",
    "\n",
    "print(y_train.shape)\n",
    "print(y_test.shape)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now train the classifier on the training dataset and test it on the unseen dataset:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn_classifier = knn_classifier.fit(X_train, y_train)\n",
    "y_pred = knn_classifier.predict(X_test)\n",
    "y_pred\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn_classifier.score(X_test, y_test)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can generate a more comprehensive accuracy report that investigated the accuracy at the individual class level:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import metrics\n",
    "print(metrics.classification_report(y_test, y_pred))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see what the confusion matrix looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(metrics.confusion_matrix(y_test, y_pred))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we would prefer to use stratified cross-fold validations, then:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.model_selection import cross_val_score\n",
    "scores = cross_val_score(knn_classifier, X_test, y_test, cv=5, scoring='accuracy')\n",
    "scores\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code above uses 5 folds and uses accuracy for a general evaluation metric. The returned result is accuracy for each of the folds.\n",
    "\n",
    "We can find the mean and standard deviation of all the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('mean is: ', scores.mean())\n",
    "print('STD is: ', scores.std())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check Mode "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# example of the majority class naive classifier in scikit-learn\n",
    "from sklearn.dummy import DummyClassifier\n",
    "from sklearn.metrics import accuracy_score\n",
    "\n",
    "# define model\n",
    "model = DummyClassifier(strategy='most_frequent')\n",
    "# fit model\n",
    "model.fit(X, y)\n",
    "# make predictions\n",
    "yhat = model.predict(X)\n",
    "# calculate accuracy\n",
    "accuracy = accuracy_score(y, yhat)\n",
    "print('Accuracy: %.3f' % accuracy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check Random Guess Accuracy "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define model\n",
    "model = DummyClassifier(strategy='uniform')\n",
    "# fit model\n",
    "model.fit(X, y)\n",
    "# make predictions\n",
    "yhat = model.predict(X)\n",
    "# calculate accuracy\n",
    "accuracy = accuracy_score(y, yhat)\n",
    "print('Accuracy: %.3f' % accuracy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Check Random Guess Accuracy Based on Stratified Distribution "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# define model\n",
    "model = DummyClassifier(strategy='stratified')\n",
    "# fit model\n",
    "model.fit(X, y)\n",
    "# make predictions\n",
    "yhat = model.predict(X)\n",
    "# calculate accuracy\n",
    "accuracy = accuracy_score(y, yhat)\n",
    "print('Accuracy: %.3f' % accuracy)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Load the student grade dataset and use the kNN classifier to predict the class grade based on all the assignment results.\n",
    "\n",
    "First train all the data and test the accuracy.\n",
    "\n",
    "Then use different number of folds to test the accuracy of the generalization of your classifiers.\n",
    "\n",
    "Lastly, experiment with using different combinations of assignment features and observe if the accuracy increases/decreases as you omit some of them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Machine Learning - Evaluating Multiple Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Working in the fields of machine learning inevitably requires the practitioner to **compare the generalizability of one (or more) algorithm against others** in order to determine which might be a better solution for a given problem.\n",
    "\n",
    "When performing such comparisons, it is important to realize that same algorithms, having different settings (such as the value for k in kNN) are seen as different algorithms and should be treated as such in the comparisons.\n",
    "\n",
    "The question is: how to best summarize a series of algorithms with different settings and their performances across multiple datasets? \n",
    "\n",
    "In such circumstances, the practitioner is referred to **statistical techniques** to provide answers. In particular, the practitioner is expected to provide summaries of every algorithm's accuracy in terms of **mean ranks** across all datasets. The mean ranks provides an informative summary of the **overall performance** of all algorithms that can then be analysed even further using **non-parametric** tests such as Friedman's test and a range of post hoc-tests. \n",
    "\n",
    "In essence, these tests evaluate if the difference in the mean ranks is statistically different enough from the expected mean. The rejection of the null-hypothesis then opens the door to detailing further which algorithm's mean ranks differ significantly from others'.\n",
    "\n",
    "Interested readers are referred to Demšar's article which provides examples on how to conduct statistical comparisons between multiple classifiers' results on multiple datasets:\n",
    "\n",
    "> Demšar, J. (2006). Statistical comparisons of classifiers over multiple data sets. The Journal of Machine Learning Research, 7, 1-30.\n",
    "\n",
    "The image below shows an example of how to display a summary of algorithms' performances using the geometric mean and the mean ranks: \n",
    "\n",
    "![Source Teo Susnjak](../figures/ml_mean_rank_example.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# No Free Lunch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Every model/classifier is a simplified representation of reality. By their very definition, simplifications discard irrelevant detail in order to enable a greater emphasis of some aspect of reality of interest for further study.  \n",
    "\n",
    "These simplifications are founded on assumptions that every machine learning algorithm embodies to varying degrees. These assumptions may hold in some situations, but not others. The consequence is, that a classifier that operates well in a certain situation well may fail in another. Making bold claims that a given machine learning algorithm is more accurate than another is therefore strongly frowned upon.\n",
    "\n",
    "In 1997, Wolpert and Macready described the “No Free Lunch” theorem which simply states that there is no one model/classifier that works best for every problem. The truth is that assumptions of a really effective and accurate classifier for one problem may not hold for different one. Because of this, it is common in machine learning to try multiple models and find one that works best for a particular problem.  This is especially true in supervised learning; validation or cross-validation is commonly used to assess the predictive accuracies of multiple models of varying complexity to find the best model.  \n",
    "\n",
    "Therefore, depending on the problem domain and requirements, it is important consider multiple factors before settling on a machine learning algorithm. One must assess the trade-offs between speed, accuracy, and complexity/interpretability of different machine learning algorithms and their classifiers, and select one that works best for that particular problem and a set of requirements."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Feature Selection $^1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The main purpose of machine learning is to produce classifiers that generalise in their predictive accuracy beyond the datasets used to train them. To a large degree, **their final accuracy is dependent on the descriptive strength and quality of the features** that constitute the training dataset. \n",
    "\n",
    "**It is often tempting to simply provide a machine learning algorithm with as many features as are available for a given dataset. However, doing so has been consistently shown to be associated with negative outcomes.**\n",
    "\n",
    "The inclusion of large feature numbers in a training dataset presents **computational challenges** that mostly arise during the training phase and can be prohibitive for some algorithms, but can also be a **strain during the detection time** for real-time systems processing high-volume data streams. Unnecessary and **redundant features** increase the search space for a machine learning algorithm. This in turn**dilutes the signal strength of a true pattern** and makes it more likely that due to the presence of noisy and irrelevant features, a spurious pattern will be discovered instead. \n",
    "\n",
    "In general it is not known *a priori* which features are meaningful, and **finding the optimal feature subset has been proven to be a NP-complete problem**. Nonetheless, it is still imperative that feature selection algorithms be applied to a dataset as a pre-processing step before training classifiers, in order to reduce feature dimensionality. \n",
    "\n",
    "**Not only are both the computational complexity and the generalisability improved by selecting the most concise subset, but the resulting model is more interpretable due to the fact that it is generated with the fewest possible number of parameters.** \n",
    "\n",
    "There are many algorithms and techniques available to perform feature selection. Some of the more commonly used are: Chi$^2$, Information Gain, PCA, LDA, Gain Ratiom Gini Index, SVM. \n",
    "\n",
    "Feature selection techniques can generally be divided into two broad categories. **Filter methods** are univariate techniques which consider the relevance of a particular feature in isolation to the other features and rank the features according to a metric. These algorithms are computationally efficient since they do not integrate the machine learning algorithm in its evaluation. However, they can be susceptible to selecting subsets of features that may not produce favourable results when combined with a chosen machine learning algorithm. These methods lack the ability to detect interactions among features as well as feature redundancy. \n",
    "\n",
    "On the other hand, **wrapper methods** overcome some of these shortcomings. They explicitly use the chosen machine learning algorithm to select the feature subsets and tend to outperform filter methods in predictive accuracy. However, these techniques exhibit bias in favour of a specific machine learning algorithm, and since they are computationally more intensive, they are also frequently impractical on large datasets.\n",
    "\n",
    "Hybrid filter-wrapper methods have been a subject of recent research due to their ability to exploit the strengths of both strategies. Hybrid approached essentially allow any combination of filter and wrapper methods to be combined. Due to this, some novel and interesting hybrid approaches have recently been proposed such as: using the union of feature-subset outputs from Information Gain, Gain Ratio, Gini Index and correlation filter methods as inputs to the the wrapper Genetic Algorithm, hybridization of the Gravitational Search Algorithm with Support Vector Machine and using Particle Swarm Optimisation-based multi-objective feature selection approach in combination with k-Nearest-Neighbour. Given their flexibility, hybrid approaches thus offer some degree of tuning the trade-offs between accuracy and performance. Nonetheless, devising a feature selection algorithm that is both highly accurate and computationally efficient is still an open question.\n",
    "\n",
    "For reasons of simplicity, we will consider only filter methods here, and more specifically we will look at Chi$^2$. Chi$^2$ performs a statistical test which ascertains if a given feature and class label are independent. A test result which indicates strong dependence between feature values and the associated class label, means that the given feature possesses discriminative ability. The scores of all feature vectors are then ranked resulting in an ordering of feature usefulness. The Chi$^2$ test does not take into account dependence between feature vectors themselves and is thus unable to detect feature redundancy.\n",
    "\n",
    "Chi$^2$ is designed to work with feature counts on categorical data that results in non-negative values. However, Chi$^2$ can be used on continuous data by discretizing the feature vectors and counting the occurrences of feature values in the given bins. \n",
    "\n",
    "> $^1$ Susnjak, T., Kerry, D., Barczak, A., Reyes, N., & Gal, Y. (2015, November). Wisdom of Crowds: An Empirical Study of Ensemble-Based Feature Selection Strategies. In Australasian Joint Conference on Artificial Intelligence (pp. 526-538). Springer International Publishing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grades = pd.read_csv('../datasets/grades_prediction_mode.csv')\n",
    "print(grades.head() )\n",
    "grades = grades.dropna()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Machine learning with no feature selection "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create numeric column for the response\n",
    "# note: features and response must both be entirely numeric!\n",
    "mapping = {'A+':0, 'A':1, 'A-':2 ,'B+':3, 'B':4, 'B-':5, 'C+':6, 'C':7, 'R':8, 'D':9,'E':10, 'DNC':11}\n",
    "#mapping = {'A+':0, 'A':0, 'A-':0 ,'B+':1, 'B':1, 'B-':1, 'C+':2, 'C':2, 'R':3, 'D':4,'E':4, 'DNC':4}\n",
    "grades['grade_num'] = grades.Grade.map(mapping)\n",
    "\n",
    "# create X (features) three different ways\n",
    "X = grades [['A1', 'A2', 'A3', 'A4', 'A5', 'Exam']]\n",
    "\n",
    "# create y (response)\n",
    "y = grades.grade_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.naive_bayes import GaussianNB\n",
    "nb = GaussianNB()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.tree import DecisionTreeClassifier\n",
    "treeclf = DecisionTreeClassifier(max_depth=3, random_state=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=1, test_size=0.2)\n",
    "X_train.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Test accuracy for NB (no feature selection):\", nb.fit(X_train, y_train).score(X_test, y_test))\n",
    "print(\"Test accuracy for Tree (no feature selection):\", treeclf.fit(X_train, y_train).score(X_test, y_test))\n",
    "print(\"Test accuracy for kNN (no feature selection):\", knn.fit(X_train, y_train).score(X_test, y_test))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('NB', metrics.classification_report(y_test, nb.predict(X_test)) )\n",
    "print('tree', metrics.classification_report(y_test, treeclf.predict(X_test)) )\n",
    "print('knn', metrics.classification_report(y_test, knn.predict(X_test)) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('NB \\n',metrics.confusion_matrix(y_test, nb.predict(X_test)) )\n",
    "print('tree \\n',metrics.confusion_matrix(y_test, treeclf.predict(X_test)) )\n",
    "print('knn \\n',metrics.confusion_matrix(y_test, knn.predict(X_test)) )\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Machine learning with feature selection"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.feature_selection import SelectKBest\n",
    "from sklearn.feature_selection import chi2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_new = SelectKBest(chi2, k=4).fit_transform(X, y)\n",
    "X_new.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(X_new, y, random_state=1, test_size=0.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Test accuracy for NB (with feature selection):\", nb.fit(X_train, y_train).score(X_test, y_test) )\n",
    "print(\"Test accuracy for Tree (with feature selection):\", treeclf.fit(X_train, y_train).score(X_test, y_test) )\n",
    "print(\"Test accuracy for knn (with feature selection):\", knn.fit(X_train, y_train).score(X_test, y_test) )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Exercise:** Given the Wine dataset, perform classification as above using all features for classification and then using a subset of the features. Split your train/test datasets 50/50. Report on the experimental findings. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "wine_df = pd.io.parsers.read_csv('../datasets/wine_data.csv' )\n",
    "wine_df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Classification Process Summarized"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. We **begin with a data set** containing multiple samples, elements, records, or instances (all are the same terms used by different disciplines). \n",
    "\n",
    "2. Each instance is a **feature vector** consists of a number of features or attributes.  \n",
    "\n",
    "3. One of the features is special: it represents the instance's class - the **class label**. Each instance **belongs to exactly one class**.\n",
    "\n",
    "4. Classification problems are either **binary** or **multiclass**.\n",
    "\n",
    "5. A number of classification algorithms are limited to only binary classification. However, multiclass problems can be **decomposed into series of binary classification problems** ie. an instance belongs to the target class or to any other class.\n",
    "\n",
    "6. A classifier takes as input an instance (i.e., a feature vector) and **produces a class label**.\n",
    "\n",
    "7. Creating and using a classifier entails a three-step process of: **training, testing, and deployment** in an application.\n",
    "\n",
    "8. We first split the existing data set into a **training set** and a **test set**. \n",
    "\n",
    "9. In the training phase, we present each instance from the training set to the classification algorithm. \n",
    "\n",
    "10. Then compare the class label produced by the algorithm to the true class label of the record in question.\n",
    "\n",
    "11. If possible, then we adjust the algorithm's **“parameters”** to achieve the greatest possible **accuracy** or, equivalently, the lowest possible **error rate**. \n",
    "\n",
    "12. The results can be **summarized** in a so-called **confusion matrix** whose entries are the number of records in each category.\n",
    "\n",
    "13. Unfortunately, the **error rate derived from the training set** (the training error) is typically **too optimistic** as an indicator of the error rate the classifier would achieve on new data — that is, on data that was not used during the learning phase. \n",
    "\n",
    "13. This is the purpose of the test set: after we have optimized the algorithm using only the training data, we let the classifier operate on the elements of the test set to see how well it classifies them. The error rate obtained in this way is the **generalization error** and is a much more reliable indicator of the accuracy of the classifier.\n",
    "\n",
    "14. Keep in mind the **trade-off** between **classifier complexity** and **overfitting**. The classifier can usually be tweaked to become more complex and  correctly learn all the training samples. But this is called overfitting and memorizing the data. On the other hand, if it is too simple, then it cannot learn the relationships within the data and both its training and generalization error will be poor; this is known as underfitting.\n",
    "\n",
    "15. Analyse the features in the dataset. Remove the features that might be redundant or irrelevant as they might compromise the generalisability of the classifier. \n",
    "\n",
    "16. Once a classifier has been developed and tested, it can be used to **classify truly new and unknown data points** — that is, data points for which the correct class label is not known. (This is in contrast to the test set, where the class labels were known but not used by the classifier when making a prediction.) \n",
    "\n",
    "Adapted from: \n",
    "> Source: Janert, P. K. (2010). Data analysis with open source tools.  O'Reilly Media, Inc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
